package spoj.pl;

/*
 * MTF - Małe Twierdzenie Fermeta
 * @author: Ewa Byra
 * 
 * wzor a^p-1 mod p=1
 * 
 * dla a takiego, że 1<a<p
 */

import java.util.Random;
import java.util.Scanner;

public class PRIME_T {

	public static void main(String[] args) {
		int k = 3, a, p;
		long t;
		boolean result;
		Random rnd = new Random();
		Scanner in = new Scanner(System.in); // wczytujemy ilosc testow
		t = in.nextLong();
		while (t != 0) {
			result=true;
			p = in.nextInt(); // wczytywanie sprawdzanej listy
			if (p > 4) {
				for (int i = 0; i < k; i++) {
					a = 2 + (int) rnd.nextInt(p - 2);
					if (Math.pow(a, p-1)% p != 1) {
						result = false;
						break;
					}
				}
			}
			if (result)
				System.out.println("TAK");
			else
				System.out.println("NIE");
			t--;
		}
		in.close();

	}

}
